package com.LeeCode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 到达最后一个房间的最少时间 I
 */

public class Code3341 {
    public static void main(String[] args) {
        int [][] moveTime = {
                {0,1},
                {1,2}
        };
        System.out.println(new Code3341().minTimeToReach(moveTime));
    }

    private static final int[][] DIRECTS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;

        int[][] dis = new int[n][m];
        for (int[] row : dis) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        dis[0][0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0, 0});

        while (true) {
            int[] point = pq.poll();
            int passTime = point[0], i = point[1], j = point[2];
            if (i == n - 1 && j == m - 1)
                return passTime;

            if (passTime > dis[i][j]) {
                continue;
            }

            int time = 1;

            for (int[] dir : DIRECTS) {
                int x = i + dir[0], y = j + dir[1];
                if (0 <= x && x < n && 0 <= y && y < m) {
                    int tryTime = Math.max(passTime, moveTime[x][y]) + time;
                    if (tryTime < dis[x][y]) {
                        dis[x][y] = tryTime;
                        pq.add(new int[]{tryTime, x, y});
                    }
                }
            }
        }
    }
}
